//
// Created by francklinson on 2021/8/28 AT 23:32.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>

using namespace std;

class Solution {
public:
    int projectionArea(vector<vector<int>> &grid) {
        // 找到每一行 每一列的最大值  求和
        int m = (int) grid.size(), n = (int) grid[0].size();
        vector<int> rowMax(m, 0);
        vector<int> colMax(n, 0);
        int ans = m * n;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                rowMax[i] = max(rowMax[i], grid[i][j]);
                colMax[j] = max(colMax[j], grid[i][j]);
                if (grid[i][j] == 0)
                    --ans;
            }
        }
        ans += accumulate(rowMax.begin(), rowMax.end(), 0);
        ans += accumulate(colMax.begin(), colMax.end(), 0);
        return ans;
    }
};
class Solution2 {  // 题解 少一些空间
public:
    int projectionArea(vector<vector<int>>& grid) {
        int N = grid.size();
        int ans = 0;

        for (int i = 0; i < N;  ++i) {
            int bestRow = 0;  // largest of grid[i][j]
            int bestCol = 0;  // largest of grid[j][i]
            for (int j = 0; j < N; ++j) {
                if (grid[i][j] > 0) ans++;  // top shadow
                bestRow = max(bestRow, grid[i][j]);
                bestCol = max(bestCol, grid[j][i]);
            }
            ans += bestRow + bestCol;
        }

        return ans;
    }
};

int main() {
    vector<vector<int>> grid{{1, 2},
                             {3, 4}};
    Solution solution;
    cout << solution.projectionArea(grid) << endl;
    return 0;
}

